# -*- coding: utf-8 -*-
#!/usr/bin/python
'''
Created on 2012/06/17

@author: Andr� Guerreiro n�5117
'''


'''
Classe LinkedList
classe para criar listas ligadas
'''
class LinkedList:
    '''
    construtor da classe
    @param N: tamanho da stack
    '''
    def __init__(self,N):
        self.apontadores_memoria = Stack(N)
        for k in range(N):
            self.apontadores_memoria.push(k)
            self.key =  [0 for k in range(N)]
            self.prev = [0 for k in range(N)]
            self.next = [0 for k in range(N)]
        
            self.head = None
    
    '''
    Função para criar os apontadores de memória
    '''
    def malloc(self, k):
        x = self.apontadores_memoria.pop()
        self.key[x] = k
        self.prev[x] = None
        self.next[x] = None
        return x
    
    '''
    Função para liberta espaço da memória
    @param x: valor a libertar
    '''
    def free(self, x):
        self.apontadores_memoria.push(x)
    
    '''
    Função para inserir valores na memória
    @param x: valor a inserir
    '''
    def insert(self, x):
                self.next[x] = self.head
                if self.head != None:
                        self.prev[self.head] = x
                self.head = x
                self.prev[x] = None
    
    '''
    Função para procurar valores na memória
    @param k: valor a procurar
    '''    
    def search(self, k):
        x = self.head
        while x != None and self.key[x] != k:
            x = self.next[x]
        return x
    
    '''
    Função para apagar valor da memória
    @param x: valor a apagar
    '''    
    def delete(self,x):
        if self.prev[x] != None:
            self.next[self.prev[x]] = self.next[x]
        else:
            self.head = self.next[x]
        if self.next[x] != None:
            self.prev[self.next[x]] = self.prev[x]
     
    '''
    função para obter valores da memória
    @param N: dimensão da memória
    '''        
    def getMyStack(self, N):
        for k in range(N):
            print "x:", k, self.head, "key: ", \
                    self.key[k], "next: ", self.next[k], \
                    "prev: ", self.prev[k]
            
    pass


'''
Classe Stack
classe para criar a memória
'''        
class Stack:
        '''
        construtor da classe
        '''
        def __init__(self, N):
                self.top = -1
                self.S = [0 for k in range(N)]
                pass
        
        '''
        verifica se a memória está vazia
        '''
        def stack_empty(self):
                if self.top == 0:
                        return True
                else:
                        return False
        '''
        introduz valor na memória
        '''
        def push(self, x):
                self.top += 1
                self.S[self.top] = x
                pass
        
        '''
        retira valor da memória
        '''
        def pop(self):
                if self.stack_empty():
                        return "underflow"
                else:
                        self.top -= 1
                        return self.S[self.top+1]
                pass
            
        '''
        converte os dados da memória numa string
        '''    
        def __str__(self):
                s = ""
                s += str(self.top+1) + ": "
                for k in range(0, self.top+1):
                        s += ' ' + str(self.S[k])
                return s
        pass
    
       
    

